package com.algorithm.string;

import java.util.Arrays;

/**
 * 参考阮一峰KPM算法解读
 */
public class PatternMatchKMP {
    public static void main(String[] args) {
        String str = "abcabdabeabc";
        String pattern = "abca";
        int start = match00(str, pattern);
        System.out.println(start);
        start = match01(str, pattern);
        System.out.println(start);
    }

    /**
     * 使用最原始的方法实现:时间复杂度0(N^2)
     *
     * @param str
     * @param pattern
     * @return
     */
    private static int match00(String str, String pattern) {
        for (int i = 0; i < str.length(); i++) {
            while (str.charAt(i) != pattern.charAt(0)) {
                i++;
            }
            if (i > str.length() - pattern.length()) {
                return -1;
            }
            for (int j = 0; j < pattern.length(); j++) {
                if (str.charAt(i + j) == pattern.charAt(j)) {
                    if (j++ == pattern.length() - 1) {
                        return i;
                    }
                } else {
                    break;
                }
            }
        }
        return -1;
    }

    /**
     * 优化前缀版 KMP算法
     * 解决原始算法的痛点:
     * 每次匹配失败都要从i+1开始重新匹配;
     * 当pattern中重复字符很多时效率低下
     * 解决方案:
     * 使用一个数组预处理模式串,记录如果匹配到模式串的某一位失败时,模式串可以直接前进的位数
     * 例如:
     * 模式串      a b d e f a b f f j a b d
     * next数组   -1 0 0 0 0 0 1 2 0 0 0 1 2 3
     *
     *                        ^
     * 当匹配到
     */
    private static int match01(String str, String pattern) {
        int[] next = getNextArray(pattern);
        System.out.println(Arrays.toString(next));

        for (int i = 0; i < str.length(); i++) {
            while (str.charAt(i) != pattern.charAt(0)) {
                i++;
            }
            if (i > str.length() - pattern.length()) {
                return -1;
            }
            for (int j = 0; j < pattern.length(); j++) {
                if (str.charAt(i + j) == pattern.charAt(j)) {
                    if (j++ == pattern.length() - 1) {
                        return i;
                    }
                } else {
                    i += j - next[j];
                    break;
                }
            }
        }

        return 0;
    }

    private static int[] getNextArray(String pattern) {
        //  第一个字符的next值是-1,因为C中的数组是从0开始的
        int[] next = new int[pattern.length()];
        next[0] = -1;
        for (int i = 0, j = -1; i < pattern.length() - 1; ) {
            //  i是主串的游标,j是模式串的游标
            //  这里的主串和模式串都是同一个字符串
            if (-1 == j ||                          //  如果模式串游标已经回退到第一个字符
                    pattern.charAt(i) == pattern.charAt(j))     //  如果匹配成功
            {
                //  两个游标都向前走一步
                ++i;
                ++j;
                //  存放当前的next值为此时模式串的游标值
                next[i] = j;
            } else                                  //  匹配不成功j就回退到上一个next值
            {
                j = next[j];
            }
        }
        return next;
    }
}
